142. 环形链表 II
142. 环形链表 II
分析
首先，对于环形指针，我们不应该用这种线性的模型来理解
而应该用下面这种模型来理解，更加合适
然后，我们需要确定是否有环，我们可以使用两个速度不相同的指针来解决这个问题，slow 指针一次只走一个元素的距离，fast 指针一次走两个元素的距离，那么这两个元素一定会在环中相遇，这是肯定的，原因很简单，因为 fast 指针比 slow 指针一次多走一个元素，只要 fast 指针移动到了 slow 指针的后面，那么由于这两个指针的相对速度是一个元素，所在在 slow 指针看来，fast 指针是在不断地追赶自己的，而且移动一次就距离就减少一个元素，也不会跳过自己，最终一定会相遇。
假设他们会相遇，那么慢指针会在环里转很多圈吗？感觉并不会，假设 slow 入环的时候，fast 刚好也转到了环的入环点（按理说此时他俩就相遇了，不过这里我们只是为了分析耗时最多的的情况），那么当 slow 走到环的中间的时候，fast 再次走到了入环点，然后当 slow 再次走到入环点的时候，fast 也再次走到入环点，slow、fast 最终相遇，我们从 slow 的角度看 fast，我们可以说一开始的时候，fast 需要追赶的距离是就是整个环的长度的，在 slow 再次走到入环点的时候，fast 可以追上 slow，而实际情况是 slow 在入环点的时候，fast 一定在环上非入环点的某个位置，所以，fast 需要追赶的距离是小于整个环的长度的，因此 fast 可以在 slow 再次走到入环点之前，追上 slow。
此时，我们设置从头节点到入环点的距离为 x，从入环点到相遇点的距离为 y，从相遇点到入环点的距离为 z, N 为相遇前，fast 在环里转了多少圈
我们可以得到方程
我们可以求出
我们可以推到出来什么
- 当 N=1 ，x=z; 这个时候，如果有一个指针从相遇点出发，一个指针从头出发，那么从相遇点出发的指针经过在环里绕几圈之后，一定会和从头出发的指针相遇。
- 当 N=2 ，x=y+z+z; 同理
- 当 N=3 ，x=2y+2z+z; 同理
因此，解题思路也就很清晰了，快慢指针相遇后，慢指针继续运动，同时让一个指针从头出发，当他跟慢指针相遇的时候，相遇的地方，就是入环点
我给这个题的解法取个名字，差速双指针：通过差速双指针先找到相遇的位置，再找到从相遇的位置出发的位置和和从头的位置出发的指针相遇的位置。
检查链表是否有环，用这种差速双指针真的非常好用，神了。
其实还有一种非常简单的方法：
这种简单的方法就是一边遍历一边 Set 记录走过的每一个节点，如果遍历的节点在 Set 中已经存在了，则表示进入回环了，
这个方法简单是简单，但是使用了高级的数据结构，没有使用基本的数据结构，效率会低一些。
解题
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
boolean notHasLoop = false;
while(true){
// 因为链表可能没有元素，也可能只有一个元素
if(fast==null || fast.next == null || fast.next.next==null){
notHasLoop = true;
break;
}
// 这个其实不用检查，因为fast一定会先检查一遍，此时已经返回了，但是为了对称，还是写吧
if(slow==null || slow.next==null){
notHasLoop = true;
break;
}
fast=fast.next.next;
slow=slow.next;
// 先移动，再对比，因为一开始这俩指针就是相等的
if(fast==slow){
break;
}
}
if(!notHasLoop){
ListNode arrow = head;
// 此时slow就在相遇点
while(arrow!=slow){
arrow=arrow.next;
slow=slow.next;
}
return slow;
}else{
return null;
}
}